A. Multiprocessor Computer
Typically, a multiprocessor computer has a number of devices, including multiple (i.e., two or more) processors, interconnected by a system bus for communication. The devices on the system bus can also include one or more memory modules and one or more input/output (I/O) units, such as disk, tape or I/O bridge controllers. Each memory module includes at least one memory bank. A memory bank is an independently accessable memory unit, such as a dynamic random access memory ("DRAM") and associated support logic.
All of the devices occupy what are known as "slots" on the system bus. A "slot" is the physical location of the interconnection for the device on the bus. Each slot on the system bus has an associated identifier, called a "SLOT ID." The number of slots determines the maximum number of devices that can be connected to the system bus.
Essentially, the memory banks on the system bus serve as shared resources for the processors and I/O units, and therefore can be called "resource nodes." The processors and I/O units can be called "commander nodes." The commander nodes initiate requests to gain control of the system bus to access the resource nodes. Upon gaining control of the system bus, the commander nodes transmit commands (e.g., read or write) over the system bus, to which the resource nodes respond.
In a known computer, the commander nodes transmit the requests and commands in synchronization with system bus cycles. The bus cycles specify periodically occurring intervals of time during which requests, commands, and data can be transmitted over the system bus. During the system bus cycles, the times when requests can be transmitted are called "request cycles." Each commander node "desiring" bus access transmits a request during one of the request cycles, typically during the next-occurring request cycle.
B. Arbitration Mechanisms
When two or more commander nodes request control of the system bus during the same request cycle, the computer employs bus arbitration to determine which of the requesting commander nodes is to gain bus control. Control is granted to or taken by the requesting commander node that wins the arbitration.
In known bus arbitration techniques, each node capable of requesting system bus access typically is assigned a priority level. An arbitration mechanism compares the priority levels of all devices that request control of the system bus during the same request cycle, and the device with the highest priority among those gains control of the bus.
Computers use either central or distributed arbitration mechanisms. In central arbitration, a single, central priority device, frequently called an "arbiter," receives all access requests during each request cycle, determines which of the requesting nodes has the highest priority, and grants that node bus access. By contrast, in distributed arbitration, each requesting node determines for itself whether it has won arbitration, i.e., whether it has sufficient priority to obtain control of the system bus. There is no central arbiter. If another node of higher priority simultaneously seeks bus access, the other node will win the arbitration, and the requesting node(s) of lower priority must wait until the next request cycle to again seek bus access by transmitting another request.
C. System BUS Transactions
A "transaction" can be defined generally as a complete logical task being performed via the system bus, entailing one or more transfers of information between nodes. Once a commander node has arbitrated for the system bus and won, it issues a command/address transfer to initiate a transaction. The "command" portion or transfer of the command/address transfer specifies the type of transaction to be performed, and the "address" portion or transfer thereof identifies the memory locations involved in the transaction. In response to the command/address transfer, data is normally sent over the system bus.
For example, a "read" transaction consists of one or more data transfers from a resource node, e.g., a memory bank, to a commander node, which follow a command/address transfer identifying the memory locations from which the data is to be retrieved. Analogously, a "write" transaction consists of one or more data transfers from a commander node to a memory bank, which follows a command/address transfer identifying the memory locations into which the transferred data is to be written.
D. Memory Bank Conflicts
Memory bank conflicts occur when two or more commander nodes request access to data stored within the same physical bank of the memory in overlapping transactions. In other words, memory bank conflicts occur when, during a first transaction involving an access request to that bank from a first commander node, a second commander node initiates a transaction to that bank. When memory bank conflicts occur, the memory bank is unable to respond in a timely way to the requesting commander nodes, whereupon system efficiency is decreased.
Various methods have also been proposed for reducing memory bank conflicts. These include, for instance, memory/slave queue structures and highly interleaved memory structures.
In a known memory/slave queue structure, in response to a command/address transfer identifying it as the memory bank being accessed (e.g., for a read transaction), the identified memory bank normally arbitrates for the system bus, and, on winning, transfers the requested data. If the memory bank can not service the "read" request when it is received, the memory bank stores the command/address information in a transaction queue buffer until the request can be serviced. Regardless of whether they must be placed in the transaction queue, the command/address transfers are typically serviced on a "first-in-first-out" basis.
If the transaction queue becomes too long, however, the transaction queue buffer can be in danger of overflowing (i.e., exceeding the storage size of the buffer), which may result in loss of stored command/address information. Consequently, in many such systems, when the transaction queue reaches a preselected length, the memory can assert an INHIBIT line or signal to prevent any of the commander nodes from issuing further access requests (i.e., command/address transfers) on the system bus. With this scheme, while the INHIBIT line is asserted, no further bus transactions are permitted, even to other memory banks that have transaction queues not in danger of overflowing. Accordingly, the throughput of the entire system can drop to zero when the INHIBIT line is asserted by any memory bank, even if other memory banks can accommodate further transactions.
In a variation on this approach, the memory bank with the lengthy transaction queue can return a "retry" response instead of asserting an INHIBIT line. A "retry" response instructs the commander nodes to retry access requests at later times. Of course, even at the later times, the requesting commander nodes may still encounter "retry" responses; consequently, this approach can significantly increase traffic on the system bus while not facilitating access to the memory resources.
The other mentioned approach, "interleaving," is the process of dividing a memory space into a series of memory units or banks, and assigning logical addresses so that adjacent sequential addresses of the memory space correspond to memory locations in different banks. For example, with four-way or (i.e., four level) interleaving, the memory space is divided into four banks: Bank No. 1 contains datawords (i.e., the minimum addressable quantities of stored dam) assigned addresses 1, 5, 9, 13, etc., bank No. 2 contains datawords assigned addresses 2, 6, 10, 14, and so forth.
For accessing data located at a series of sequential addresses, the interleaving permits the memory to operate in an overlapping fashion to provide the data four times as fast as a non-interleaved memory could do. Two-way interleaving reduces the probability of a memory conflict by 50% (i.e., by 1/M, where "M" is the number of ways the memory is interleaved).
A drawback with conventional interleaving schemes is that they do not "resolve" memory bank conflicts that do arise. With the sizes of DRAM's increasing significantly with each new generation of computers, the probability of memory bank conflicts can be significant, even with highly interleaved memories.
Another source of memory conflicts can be masked write operations. A masked write operation, which is sometimes referred to as a "read-modify-write" (RMW), consists of a read operation followed by a write operation. The read operation obtains the requisite byte transfer size of data from the memory, including the data from the locations to which data is to written. The commander node then over-writes the bytes that occupy those data locations, and the previously read data, with the modified bytes, are then written back to memory during the write portion of the operation.
If a masked write operation is not "atomic," another commander node can concurrently read data from or write data to the same memory locations involved in the masked write operation. In that case, the data being processed by one or the other commander nodes, or being written to memory, may be not correct or not current, i.e., in short, "dirty." Unpredictable results affecting system integrity can occur when this happens.
A known technique for providing atomic transactions to avoid such memory bank conflicts involves an exclusive access command, such as an "interlock read" command. This technique uses a "lock" indicator or bit in a memory bank, which is set when the "read" portion of a masked write operation is performed and which is reset after the "write" portion is completed. In response to an attempted read or write operation by another commander node to the same memory locations after the lock bit is set, the memory returns lock status information to that commander node to indicate that the second read command was not accepted by the memory. A system including a memory lock indicator is described in U.S. Pat. No. 4,937,733.
The interlock read operation alleviates problems caused by multiple processors attempting to perform conflicting operations; however, commander nodes may repeatedly encounter locked memory locations and thus may not be able to obtain needed access to memory resources in a timely manner.